/*
 * Copyright (C) 2002-2017 Sebastiano Vigna
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.intellij.util.containers;

import gnu.trove.TObjectHashingStrategy;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.*;

/**
 * A type-specific linked hash set with with a fast, small-footprint
 * implementation.
 *
 * <p>
 * Instances of this class use a hash table to represent a set. The table is
 * filled up to a specified <em>load factor</em>, and then doubled in size to
 * accommodate new entries. If the table is emptied below <em>one fourth</em> of
 * the load factor, it is halved in size; however, the table is never reduced to
 * a size smaller than that at creation time: this approach makes it possible to
 * create sets with a large capacity in which insertions and deletions do not
 * cause immediately rehashing. Moreover, halving is not performed when deleting
 * entries from an iterator, as it would interfere with the iteration process.
 *
 * <p>
 * Note that {@link #clear()} does not modify the hash table size.
 *
 * <p>
 * Iterators generated by this set will enumerate elements in the same order in
 * which they have been added to the set (addition of elements already present
 * in the set does not change the iteration order). Note that this order has
 * nothing in common with the natural order of the keys. The order is kept by
 * means of a doubly linked list, represented <i>via</i> an array of longs
 * parallel to the table.
 *
 * <p>
 * The iterators provided by this class are type-specific
 * {@linkplain java.util.ListIterator list iterators}, and can be started at any
 * element <em>which is in the set</em> (if the provided element is not in the
 * set, a {@link NoSuchElementException} exception will be thrown). If, however,
 * the provided element is not the first or last element in the set, the first
 * access to the list index will require linear time, as in the worst case the
 * entire set must be scanned in iteration order to retrieve the positional
 * index of the starting element.
 */
public class ObjectLinkedOpenHashSet<K> extends AbstractSet<K> implements Set<K>, Serializable, Cloneable {
  private static final long serialVersionUID = 0L;

  private static final long UNSIGNED_INT_MAX_VALUE = 0xFFFFFFFFL;
  /**
   * The initial default size of a hash table.
   */
  private static final int DEFAULT_INITIAL_SIZE = 16;
  /**
   * The default load factor of a hash table.
   */
  private static final float DEFAULT_LOAD_FACTOR = .75f;
  /**
   * The default object hashing strategy
   */
  private static final TObjectHashingStrategy DEFAULT_HASHING_STRATEGY = TObjectHashingStrategy.CANONICAL;
  /**
   * The array of keys.
   */
  transient K[] key;
  /**
   * The strategy used to hash objects in this collection.
   */
  protected final TObjectHashingStrategy<K> hashingStrategy;
  /**
   * The mask for wrapping a position counter.
   */
  private transient int mask;
  /**
   * Whether this set contains the null key.
   */
  transient boolean containsNull;

  /**
   * The index of the first entry in iteration order. It is valid iff
   * {@link #size} is nonzero; otherwise, it contains -1.
   */
  private transient int first = -1;
  /**
   * The index of the last entry in iteration order. It is valid iff {@link #size}
   * is nonzero; otherwise, it contains -1.
   */
  private transient int last = -1;
  /**
   * For each entry, the next and the previous entry in iteration order, stored as
   * {@code ((prev & 0xFFFFFFFFL) << 32) | (next & 0xFFFFFFFFL)}. The first entry
   * contains predecessor -1, and the last entry contains successor -1.
   */
  private transient long[] link;
  /**
   * The current table size. Note that an additional element is allocated for
   * storing the null key.
   */
  transient int n;
  /**
   * Threshold after which we rehash. It must be the table size times {@link #f}.
   */
  private transient int maxFill;
  /**
   * We never resize below this threshold, which is the construction-time {#n}.
   */
  private final transient int minN;
  /**
   * Number of entries in the set (including the null key, if present).
   */
  private int size;
  /**
   * The acceptable load factor.
   */
  private final float f;

  /**
   * Creates a new hash set with initial expected
   * {@link ObjectLinkedOpenHashSet#DEFAULT_INITIAL_SIZE} elements and
   * {@link ObjectLinkedOpenHashSet#DEFAULT_LOAD_FACTOR} as load factor
   * {@link ObjectLinkedOpenHashSet#DEFAULT_HASHING_STRATEGY} default hashing strategy
   */
  public ObjectLinkedOpenHashSet() {
    this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR);
  }

  /**
   * Creates a new hash set with {@link ObjectLinkedOpenHashSet#DEFAULT_LOAD_FACTOR} as load factor
   * and with default hashing strategy {@link ObjectLinkedOpenHashSet#DEFAULT_HASHING_STRATEGY}
   *
   * @param expected the expected number of elements in the hash set.
   */
  public ObjectLinkedOpenHashSet(final int expected) {
    this(expected, DEFAULT_LOAD_FACTOR);
  }

  /**
   * Creates a new hash set with initial expected
   * @param strategy {@link TObjectHashingStrategy} used to compute hash codes and to compare objects.
   */
  public ObjectLinkedOpenHashSet(TObjectHashingStrategy<K> strategy) {
    this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR, strategy);
  }

  /**
   * Creates a new hash set with {@link ObjectLinkedOpenHashSet#DEFAULT_LOAD_FACTOR} as load factor
   * copying a given collection and with default hashing strategy {@link ObjectLinkedOpenHashSet#DEFAULT_HASHING_STRATEGY}
   *
   * @param c a {@link Collection} to be copied into the new hash set.
   */
  public ObjectLinkedOpenHashSet(final Collection<? extends K> c) {
    this(c.size(), DEFAULT_LOAD_FACTOR);
    addAll(c);
  }

  /**
   * Creates a new hash set with {@link ObjectLinkedOpenHashSet#DEFAULT_LOAD_FACTOR} as load factor.
   *
   * @param expected the expected number of elements in the hash set.
   * @param strategy {@link TObjectHashingStrategy} used to compute hash codes and to compare objects.
   */
  public ObjectLinkedOpenHashSet(final int expected, TObjectHashingStrategy<K> strategy) {
    this(expected, DEFAULT_LOAD_FACTOR, strategy);
  }

  /**
   * Creates a new hash set with {@link ObjectLinkedOpenHashSet#DEFAULT_LOAD_FACTOR} as load factor
   * copying a given collection.
   *
   * @param c a {@link Collection} to be copied into the new hash set.
   * @param strategy {@link TObjectHashingStrategy} used to compute hash codes and to compare objects.
   */
  public ObjectLinkedOpenHashSet(final Collection<? extends K> c, TObjectHashingStrategy<K> strategy) {
    this(c.size(), DEFAULT_LOAD_FACTOR , strategy);
    addAll(c);
  }

  /**
   * Creates a new hash set. The actual table size will be the least power of two greater than
   * {@code expected}/{@code f}.
   *
   * @param expected the expected number of elements in the hash set.
   * @param f        the load factor.
   */
  @SuppressWarnings("unchecked")
  public ObjectLinkedOpenHashSet(final int expected, final float f) {
    this(expected, f, DEFAULT_HASHING_STRATEGY);
  }

  /**
   * Creates a new hash set. The actual table size will be the least power of two greater than
   * {@code expected}/{@code f}.
   *
   * @param expected the expected number of elements in the hash set.
   * @param f        the load factor.
   * @param strategy {@link TObjectHashingStrategy} used to compute hash codes and to compare objects.
   */
  @SuppressWarnings("unchecked")
  public ObjectLinkedOpenHashSet(final int expected, final float f, TObjectHashingStrategy<K> strategy) {
    if (f <= 0 || f > 1) {
      throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1");
    }
    if (expected < 0) {
      throw new IllegalArgumentException("The expected number of elements must be nonnegative");
    }
    this.f = f;
    minN = n = arraySize(expected, f);
    mask = n - 1;
    maxFill = maxFill(n, f);
    key = (K[])new Object[n + 1];
    link = new long[n + 1];
    hashingStrategy = strategy;
  }

  private int realSize() {
    return containsNull ? size - 1 : size;
  }

  private void ensureCapacity(final int capacity) {
    final int needed = arraySize(capacity, f);
    if (needed > n) {
      rehash(needed);
    }
  }

  private void tryCapacity(final long capacity) {
    final int needed = (int)Math.min(1 << 30, Math.max(2, nextPowerOfTwo((long)Math.ceil(capacity / f))));
    if (needed > n) {
      rehash(needed);
    }
  }

  @Override
  public boolean addAll(Collection<? extends K> c) {
    // The resulting collection will be at least c.size() big
    if (f <= 0.5) {
      ensureCapacity(c.size()); // The resulting collection will be sized for c.size() elements
    }
    else {
      tryCapacity(size() + c.size()); // The resulting collection will be tentatively sized for size() + c.size()
    }
    // elements
    return super.addAll(c);
  }

  @Override
  public boolean add(final K k) {
    int pos;
    if (k == null) {
      if (containsNull) {
        return false;
      }
      pos = n;
      containsNull = true;
    }
    else {
      K curr;
      final K[] key = this.key;
      // The starting point.
      if ((curr = key[pos = mix(hashingStrategy.computeHashCode(k)) & mask]) != null) {
        if (hashingStrategy.equals(curr,k)) {
          return false;
        }
        while ((curr = key[pos = pos + 1 & mask]) != null) {
          if (hashingStrategy.equals(curr, k)) {
            return false;
          }
        }
      }
      key[pos] = k;
    }
    if (size == 0) {
      first = last = pos;
      // Special case of SET_UPPER_LOWER(link[pos], -1, -1);
      link[pos] = -1L;
    }
    else {
      link[last] ^= (link[last] ^ pos & UNSIGNED_INT_MAX_VALUE) & UNSIGNED_INT_MAX_VALUE;
      link[pos] = (last & UNSIGNED_INT_MAX_VALUE) << 32 | UNSIGNED_INT_MAX_VALUE;
      last = pos;
    }
    if (size++ >= maxFill) {
      rehash(arraySize(size + 1, f));
    }
    return true;
  }

  /**
   * Add a random element if not present, get the existing value if already
   * present.
   * <p>
   * This is equivalent to (but faster than) doing a:
   *
   * <pre>
   * K exist = set.get(k);
   * if (exist == null) {
   * 	set.add(k);
   * 	exist = k;
   * }
   * </pre>
   */
  public K addOrGet(final K k) {
    int pos;
    if (k == null) {
      if (containsNull) {
        return key[n];
      }
      pos = n;
      containsNull = true;
    }
    else {
      K curr;
      final K[] key = this.key;
      // The starting point.
      if ((curr = key[pos = mix(hashingStrategy.computeHashCode(k)) & mask]) != null) {
        if (hashingStrategy.equals(curr, k)) {
          return curr;
        }
        while ((curr = key[pos = pos + 1 & mask]) != null) {
          if (hashingStrategy.equals(curr, k)) {
            return curr;
          }
        }
      }
      key[pos] = k;
    }
    if (size == 0) {
      first = last = pos;
      // Special case of SET_UPPER_LOWER(link[pos], -1, -1);
      link[pos] = -1L;
    }
    else {
      link[last] ^= (link[last] ^ pos & UNSIGNED_INT_MAX_VALUE) & UNSIGNED_INT_MAX_VALUE;
      link[pos] = (last & UNSIGNED_INT_MAX_VALUE) << 32 | UNSIGNED_INT_MAX_VALUE;
      last = pos;
    }
    if (size++ >= maxFill) {
      rehash(arraySize(size + 1, f));
    }
    return k;
  }

  /**
   * Shifts left entries with the specified hash code, starting at the specified
   * position, and empties the resulting free entry.
   *
   * @param pos a starting position.
   */
  private void shiftKeys(int pos) {
    // Shift entries with the same hash.
    int last, slot;
    K curr;
    final K[] key = this.key;
    for (;;) {
      last = pos;
      pos = pos + 1 & mask;
      for (;;) {
        if ((curr = key[pos]) == null) {
          key[last] = null;
          return;
        }
        slot = mix(hashingStrategy.computeHashCode(curr)) & mask;
        if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) {
          break;
        }
        pos = pos + 1 & mask;
      }
      key[last] = curr;
      fixPointers(pos, last);
    }
  }

  private boolean removeEntry(final int pos) {
    size--;
    fixPointers(pos);
    shiftKeys(pos);
    if (n > minN && size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) {
      rehash(n / 2);
    }
    return true;
  }

  private boolean removeNullEntry() {
    containsNull = false;
    key[n] = null;
    size--;
    fixPointers(n);
    if (n > minN && size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) {
      rehash(n / 2);
    }
    return true;
  }

  @Override
  public boolean remove(final Object k) {
    if (k == null) {
      if (containsNull) return removeNullEntry();
      return false;
    }
    K curr;
    K key = (K)k;
    final K[] keyArray = this.key;
    int pos;
    // The starting point.
    if ((curr = keyArray[pos = mix(hashingStrategy.computeHashCode(key)) & mask]) == null) return false;
    if (hashingStrategy.equals(key, curr)) return removeEntry(pos);
    while (true) {
      if ((curr = keyArray[pos = pos + 1 & mask]) == null) return false;
      if (hashingStrategy.equals(key, curr)) return removeEntry(pos);
    }
  }

  @Override
  public boolean contains(final Object k) {
    if (k == null) {
      return containsNull;
    }
    K curr;
    K key = (K)k;
    final K[] keyArray = this.key;
    int pos;
    // The starting point.
    if ((curr = keyArray[pos = mix(hashingStrategy.computeHashCode(key)) & mask]) == null) return false;
    if (hashingStrategy.equals(key, curr)) return true;
    while (true) {
      if ((curr = keyArray[pos = pos + 1 & mask]) == null) return false;
      if (hashingStrategy.equals(key, curr)) return true;
    }
  }

  /**
   * Returns the element of this set that is equal to the given key, or
   * {@code null}.
   *
   * @return the element of this set that is equal to the given key, or
   * {@code null}.
   */
  public K get(final Object k) {
    if (k == null) return key[n]; // This is correct independently of the value of containsNull and of the set
    // being custom
    K curr;
    K key = (K)k;
    final K[] keyArray = this.key;
    int pos;
    // The starting point.
    if ((curr = keyArray[pos = mix(hashingStrategy.computeHashCode(key)) & mask]) == null) return null;
    if (hashingStrategy.equals(key, curr)) return curr;
    // There's always an unused entry.
    while (true) {
      if ((curr = keyArray[pos = pos + 1 & mask]) == null) return null;
      if (hashingStrategy.equals(key, curr)) return curr;
    }
  }

  /*
   * Removes all elements from this set.
   *
   * <p>To increase object reuse, this method does not change the table size.
   *
   */
  @Override
  public void clear() {
    if (size == 0) {
      return;
    }
    size = 0;
    containsNull = false;
    Arrays.fill(key, null);
    first = last = -1;
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * Modifies the {@link #link} vector so that the given entry is removed. This
   * method will complete in constant time.
   *
   * @param i the index of an entry.
   */
  private void fixPointers(final int i) {
    if (size == 0) {
      first = last = -1;
      return;
    }
    if (first == i) {
      first = (int)link[i];
      if (0 <= first) {
        // Special case of SET_PREV(link[first], -1)
        link[first] |= UNSIGNED_INT_MAX_VALUE << 32;
      }
      return;
    }
    if (last == i) {
      last = (int)(link[i] >>> 32);
      if (0 <= last) {
        // Special case of SET_NEXT(link[last], -1)
        link[last] |= UNSIGNED_INT_MAX_VALUE;
      }
      return;
    }
    final long linki = link[i];
    final int prev = (int)(linki >>> 32);
    final int next = (int)linki;
    link[prev] ^= (link[prev] ^ linki & UNSIGNED_INT_MAX_VALUE) & UNSIGNED_INT_MAX_VALUE;
    link[next] ^= (link[next] ^ linki & 0xFFFFFFFF00000000L) & 0xFFFFFFFF00000000L;
  }

  /**
   * Modifies the {@link #link} vector for a shift from s to d. This method will
   * complete in constant time.
   *
   * @param s the source position.
   * @param d the destination position.
   */
  private void fixPointers(int s, int d) {
    if (size == 1) {
      first = last = d;
      // Special case of SET(link[d], -1, -1)
      link[d] = -1L;
      return;
    }
    if (first == s) {
      first = d;
      link[(int)link[s]] ^= (link[(int)link[s]] ^ (d & UNSIGNED_INT_MAX_VALUE) << 32) & 0xFFFFFFFF00000000L;
      link[d] = link[s];
      return;
    }
    if (last == s) {
      last = d;
      link[(int)(link[s] >>> 32)] ^= (link[(int)(link[s] >>> 32)] ^ d & UNSIGNED_INT_MAX_VALUE) & UNSIGNED_INT_MAX_VALUE;
      link[d] = link[s];
      return;
    }
    final long links = link[s];
    final int prev = (int)(links >>> 32);
    final int next = (int)links;
    link[prev] ^= (link[prev] ^ d & UNSIGNED_INT_MAX_VALUE) & UNSIGNED_INT_MAX_VALUE;
    link[next] ^= (link[next] ^ (d & UNSIGNED_INT_MAX_VALUE) << 32) & 0xFFFFFFFF00000000L;
    link[d] = links;
  }

  /**
   * A list iterator over a linked set.
   *
   * <p>
   * This class provides a list iterator over a linked hash set. The constructor
   * runs in constant time.
   */
  private class SetIterator implements ListIterator<K> {
    /**
     * The entry that will be returned by the next call to
     * {@link java.util.ListIterator#previous()} (or {@code null} if no previous
     * entry exists).
     */
    int prev = -1;
    /**
     * The entry that will be returned by the next call to
     * {@link java.util.ListIterator#next()} (or {@code null} if no next entry
     * exists).
     */
    int next;
    /**
     * The last entry that was returned (or -1 if we did not iterate or used
     * {@link #remove()}).
     */
    int curr = -1;
    /**
     * The current index (in the sense of a {@link java.util.ListIterator}). When
     * -1, we do not know the current index.
     */
    int index;

    SetIterator() {
      next = first;
      index = 0;
    }

    @Override
    public boolean hasNext() {
      return next != -1;
    }

    @Override
    public boolean hasPrevious() {
      return prev != -1;
    }

    @Override
    public K next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      curr = next;
      next = (int)link[curr];
      prev = curr;
      if (index >= 0) {
        index++;
      }
      return key[curr];
    }

    @Override
    public K previous() {
      if (!hasPrevious()) throw new NoSuchElementException();
      curr = prev;
      prev = (int)(link[curr] >>> 32);
      next = curr;
      if (index >= 0) {
        index--;
      }
      return key[curr];
    }

    private void ensureIndexKnown() {
      if (index >= 0) {
        return;
      }
      if (prev == -1) {
        index = 0;
        return;
      }
      if (next == -1) {
        index = size;
        return;
      }
      int pos = first;
      index = 1;
      while (pos != prev) {
        pos = (int)link[pos];
        index++;
      }
    }

    @Override
    public int nextIndex() {
      ensureIndexKnown();
      return index;
    }

    @Override
    public int previousIndex() {
      ensureIndexKnown();
      return index - 1;
    }

    @Override
    public void remove() {
      ensureIndexKnown();
      if (curr == -1) throw new IllegalStateException();
      if (curr == prev) {
        /*
         * If the last operation was a next(), we are removing an entry that preceeds
         * the current index, and thus we must decrement it.
         */
        index--;
        prev = (int)(link[curr] >>> 32);
      }
      else {
        next = (int)link[curr];
      }
      size--;
      /*
       * Now we manually fix the pointers. Because of our knowledge of next and prev,
       * this is going to be faster than calling fixPointers().
       */
      if (prev == -1) {
        first = next;
      }
      else {
        link[prev] ^= (link[prev] ^ next & UNSIGNED_INT_MAX_VALUE) & UNSIGNED_INT_MAX_VALUE;
      }
      if (next == -1) {
        last = prev;
      }
      else {
        link[next] ^= (link[next] ^ (prev & UNSIGNED_INT_MAX_VALUE) << 32) & 0xFFFFFFFF00000000L;
      }
      int last, slot, pos = curr;
      curr = -1;
      if (pos == n) {
        ObjectLinkedOpenHashSet.this.containsNull = false;
        ObjectLinkedOpenHashSet.this.key[n] = null;
      }
      else {
        K curr;
        final K[] key = ObjectLinkedOpenHashSet.this.key;
        // We have to horribly duplicate the shiftKeys() code because we need to update
        // next/prev.
        for (;;) {
          last = pos;
          pos = pos + 1 & mask;
          for (;;) {
            if ((curr = key[pos]) == null) {
              key[last] = null;
              return;
            }
            slot = mix(hashingStrategy.computeHashCode(curr)) & mask;
            if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) {
              break;
            }
            pos = pos + 1 & mask;
          }
          key[last] = curr;
          if (next == pos) {
            next = last;
          }
          if (prev == pos) {
            prev = last;
          }
          fixPointers(pos, last);
        }
      }
    }

    /**
     * Replaces the last element returned by {@link #next} or {@link #previous} with
     * the specified element (optional operation).
     *
     * @param k the element used to replace the last element returned.
     *
     *          <p>
     *          This default implementation just throws an
     *          {@link UnsupportedOperationException}.
     * @see ListIterator#set(Object)
     */
    @Override
    public void set(final K k) {
      throw new UnsupportedOperationException();
    }

    /**
     * Inserts the specified element into the list (optional operation).
     *
     * <p>
     * This default implementation just throws an
     * {@link UnsupportedOperationException}.
     *
     * @param k the element to insert.
     * @see ListIterator#add(Object)
     */
    @Override
    public void add(final K k) {
      throw new UnsupportedOperationException();
    }
  }

  /**
   * Returns a type-specific list iterator on the elements in this set, starting
   * from the first element. Please see the class documentation for implementation
   * details.
   *
   * @return a type-specific list iterator starting at the first element.
   */
  @Override
  public Iterator<K> iterator() {
    return new SetIterator();
  }

  /**
   * Rehashes the set.
   *
   * <p>
   * This method implements the basic rehashing strategy, and may be overridden by
   * subclasses implementing different rehashing strategies (e.g., disk-based
   * rehashing). However, you should not override this method unless you
   * understand the internal workings of this class.
   *
   * @param newN the new size
   */
  @SuppressWarnings("unchecked")
  private void rehash(final int newN) {
    final K[] key = this.key;
    final int mask = newN - 1; // Note that this is used by the hashing macro
    final K[] newKey = (K[])new Object[newN + 1];
    int i = first, prev = -1, newPrev = -1, t, pos;
    final long[] link = this.link;
    final long[] newLink = new long[newN + 1];
    first = -1;
    for (int j = size; j-- != 0; ) {
      if (key[i] == null) {
        pos = newN;
      }
      else {
        pos = mix(hashingStrategy.computeHashCode(key[i])) & mask;
        while (newKey[pos] != null) {
          pos = pos + 1 & mask;
        }
      }
      newKey[pos] = key[i];
      if (prev != -1) {
        newLink[newPrev] ^= (newLink[newPrev] ^ pos & UNSIGNED_INT_MAX_VALUE) & UNSIGNED_INT_MAX_VALUE;
        newLink[pos] ^= (newLink[pos] ^ (newPrev & UNSIGNED_INT_MAX_VALUE) << 32) & 0xFFFFFFFF00000000L;
        newPrev = pos;
      }
      else {
        newPrev = first = pos;
        // Special case of SET(newLink[pos], -1, -1);
        newLink[pos] = -1L;
      }
      t = i;
      i = (int)link[i];
      prev = t;
    }
    this.link = newLink;
    this.last = newPrev;
    if (newPrev != -1)
    // Special case of SET_NEXT(newLink[newPrev], -1);
    {
      newLink[newPrev] |= UNSIGNED_INT_MAX_VALUE;
    }
    n = newN;
    this.mask = mask;
    maxFill = maxFill(n, f);
    this.key = newKey;
  }

  /**
   * Returns a deep copy of this set.
   *
   * <p>
   * This method performs a deep copy of this hash set; the data stored in the
   * set, however, is not cloned. Note that this makes a difference only for
   * object keys.
   *
   * @return a deep copy of this set.
   */
  @Override
  @SuppressWarnings("unchecked")
  public ObjectLinkedOpenHashSet<K> clone() {
    ObjectLinkedOpenHashSet<K> c;
    try {
      c = (ObjectLinkedOpenHashSet<K>)super.clone();
    }
    catch (CloneNotSupportedException cantHappen) {
      throw new InternalError();
    }
    c.key = key.clone();
    c.containsNull = containsNull;
    c.link = link.clone();
    return c;
  }

  /**
   * Returns a hash code for this set.
   * <p>
   * This method overrides the generic method provided by the superclass. Since
   * {@code equals()} is not overridden, it is important that the value returned by
   * this method is the same value as the one returned by the overridden method.
   *
   * @return a hash code for this set.
   */
  @Override
  public int hashCode() {
    int h = 0;
    for (int j = realSize(), i = 0; j-- != 0; ) {
      while (key[i] == null) {
        i++;
      }
      if (this != key[i]) {
        h += hashingStrategy.computeHashCode(key[i]);
      }
      i++;
    }
    // Zero / null have hash zero.
    return h;
  }

  @Override
  public boolean equals(final Object o) {
    if (o == this) {
      return true;
    }
    if (!(o instanceof Set)) {
      return false;
    }
    Set<?> s = (Set<?>)o;
    if (s.size() != size()) {
      return false;
    }
    return containsAll(s);
  }

  @Override
  public String toString() {
    final StringBuilder s = new StringBuilder();
    final Iterator<K> i = iterator();
    int n = size();
    Object k;
    boolean first = true;
    s.append("{");
    while (n-- != 0) {
      if (first) {
        first = false;
      }
      else {
        s.append(", ");
      }
      k = i.next();
      if (this == k) {
        s.append("(this collection)");
      }
      else {
        s.append(k);
      }
    }
    s.append("}");
    return s.toString();
  }

  private void writeObject(ObjectOutputStream s) throws IOException {
    final Iterator<K> i = iterator();
    s.defaultWriteObject();
    for (int j = size; j-- != 0; ) {
      s.writeObject(i.next());
    }
  }

  @SuppressWarnings("unchecked")
  private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    n = arraySize(size, f);
    maxFill = maxFill(n, f);
    mask = n - 1;
    final K[] key = this.key = (K[])new Object[n + 1];
    final long[] link = this.link = new long[n + 1];
    int prev = -1;
    first = last = -1;
    K k;
    for (int i = size, pos; i-- != 0; ) {
      k = (K)s.readObject();
      if (k == null) {
        pos = n;
        containsNull = true;
      }
      else {
        if (key[pos = mix(hashingStrategy.computeHashCode(k)) & mask] != null) {
          while (key[pos = pos + 1 & mask] != null) ;
        }
      }
      key[pos] = k;
      if (first != -1) {
        link[prev] ^= (link[prev] ^ pos & UNSIGNED_INT_MAX_VALUE) & UNSIGNED_INT_MAX_VALUE;
        link[pos] ^= (link[pos] ^ (prev & UNSIGNED_INT_MAX_VALUE) << 32) & 0xFFFFFFFF00000000L;
        prev = pos;
      }
      else {
        prev = first = pos;
        // Special case of SET_PREV(newLink[pos], -1);
        link[pos] |= UNSIGNED_INT_MAX_VALUE << 32;
      }
    }
    last = prev;
    if (prev != -1)
    // Special case of SET_NEXT(link[prev], -1);
    {
      link[prev] |= UNSIGNED_INT_MAX_VALUE;
    }
  }

  private static long nextPowerOfTwo(long x) {
    if (x == 0) {
      return 1;
    }
    else {
      --x;
      x |= x >> 1;
      x |= x >> 2;
      x |= x >> 4;
      x |= x >> 8;
      x |= x >> 16;
      return (x | x >> 32) + 1L;
    }
  }

  private static int mix(int x) {
    int h = x * -1640531527;
    return h ^ h >>> 16;
  }

  private static int maxFill(int n, float f) {
    return Math.min((int)Math.ceil(n * f), n - 1);
  }

  private static int arraySize(int expected, float f) {
    long s = Math.max(2, nextPowerOfTwo((long)Math.ceil(expected / f)));
    if (s > 1073741824) {
      throw new IllegalArgumentException("Too large (" + expected + " expected elements with load factor " + f + ")");
    }
    else {
      return (int)s;
    }
  }
}

